#include "HeapSorter.hpp"

HeapSorter::HeapSorter() {

}

HeapSorter::~HeapSorter() {

}

HeapSorter::HeapSorter(const HeapSorter& orig) {

}

void HeapSorter::screening(OwnCollections::ArrayList<int>& vector, int i, int n) {
    int leftIndex, rightIndex;
    int swapIndex;

    i++;

    while (2 * i <= n) {
        leftIndex = 2 * i;
        rightIndex = (leftIndex + 1 <= n) ? leftIndex + 1 : i;

        // Если условие выполнено, то условие пирамиды для array[i-1] выполняется
        if (vector[i - 1] >= vector[leftIndex - 1] &&
                vector[i - 1] >= vector[rightIndex - 1]) {
            return;
        }

        // Если условие не верно, то условие пирамиды для array[i-1] не выполняется.
        // чтобы оно выполнялось, нужно обменять array[i - 1] с наибольшим из
        // поддеревьев и повторить процедуру для того элемента, с котороым
        // произошел обмен
        swapIndex = (vector[leftIndex - 1] >= vector[rightIndex - 1]) ? leftIndex : rightIndex;
        vector.swap(i - 1, swapIndex - 1);
        i = swapIndex;
    }
}

void HeapSorter::sort(OwnCollections::ArrayList<int>& vector) {
    int vectorSize = vector.getCount();
 
    // Построение пирамиды 
    for (int i = vectorSize / 2; i >= 0; i--) {
      screening(vector, i, vectorSize);
    }
 

    for (int i = vectorSize-1; i > 0; i--) {
        vector.swap( 0, i );
        screening(vector, 0, i);
    }
}
